//
// Created by LiuYou on 2021/12/3.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>


static int randomNumberFromTheRange(int left, int right) {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    std::uniform_int_distribution<> uniformIntDistribution( left, right );
    return uniformIntDistribution( randomEngine );
}


/**
 * @brief 将数组元素的组织结构构建成一个堆(大顶堆)。
 * @param arr 数组元素
 * @param index 这个下标位置加入堆。
 * @param heapSize 堆的大小。
 *
 * @note 构建一个大顶堆。
 */
static void heapify(std::vector<int>& arr, int index, int heapSize) {
    int leftChildIndex = index * 2 + 1;

    while (leftChildIndex < heapSize) {
        int largestIndex{};
        if ((leftChildIndex + 1 <= heapSize - 1) && arr[leftChildIndex + 1] > arr[leftChildIndex]) {
            largestIndex = leftChildIndex + 1;
        } else {
            largestIndex = leftChildIndex;
        }

        if (arr[index] < arr[largestIndex]) {
            std::swap( arr[index], arr[largestIndex] );

            index = largestIndex;
            leftChildIndex = index * 2 + 1;
        } else {
            break;
        }
    }
}


static void heapSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    for (int i = arr.size() - 1; i >= 0; --i) {
        heapify( arr, i, arr.size());
    }

    int heapSize = arr.size();

    while (heapSize > 0) {
        std::swap( arr[0], arr[--heapSize] );
        heapify( arr, 0, heapSize );
    }

}


int main(int argc, char** argv) {
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = randomNumberFromTheRange( 0, 100 );
        }
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        // 这个 for循环构建了一个堆结构。
        for (int i = arr.size() - 1; i >= 0; --i) {
            heapify( arr, i, arr.size());
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;
    }

    std::cout << "=====================[ heap sort ]=========================" << std::endl;

    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = randomNumberFromTheRange( 0, 100 );
        }
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        heapSort( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

    }


    return 0;
}
